package com.sise.DP;

/**
 *      309. 最佳买卖股票时机含冷冻期
 *
 *      给定一个整数数组，其中第i个元素代表了第i天的股票价格 。
 *      设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
 *      你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *      卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 *
 *      输入: [1,2,3,0,2]
 *      输出: 3
 *      解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 *
 *      题解：
 *          只关注卖出的那一天
 *          所以对于每一天i，都有可能是三种状态：
 *              0 ：持股,定义其最大收益dp[i][0]；
 *              1 ：不持股且当天卖出了，定义其最大收益dp[i][1]；
 *              2 ：不持股且当天没卖出,定义其最大收益dp[i][2];
 *
 */
public class _309_maxProfit {
    public int maxProfit(int[] prices) {

        if (prices == null || prices.length == 0) return 0;

        int length = prices.length;
        // dp[i][0] : 持有股票
        // dp[i][1] : 不持有股票，本日卖出，下一天为冷冻期
        // dp[i][2] : 不持有股票，本日无卖出，下一天非冷冻期
        int[][] dp = new int[length][3];

        // base case
        dp[0][0] = -prices[0];              // 1: 第一天持有，只有可能是买入
        dp[0][1] = Integer.MIN_VALUE;       // 2. 第0天，相当于当天买入卖出，没有收益，并造成下一天冷冻期，减少选择。综合认为是负收益
        dp[0][2] = 0;                       // 3. 相当于没买入，收益自然为0

        // 下面 dp[][] 中的 i 表示的是当天的状态，而不是下一天的状态
        for (int i = 1; i < length; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]);    // 持有股票 : 1.昨天持有股票 2.本日买入（条件：昨天不持有，且不是卖出）
            dp[i][1] = dp[i-1][0] + prices[i];                          // 本日卖出 : (条件:昨天持有) 昨天持股的收益 + 今天卖出的钱
            dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);                // 不持有，但也不是卖出 : 1.昨天卖出，不持有  2.昨天没卖出，但也不持有
        }

        return Math.max(dp[length - 1][1], dp[length - 1][2]);          // 最后一天还持有股票是没有意义的,肯定是不持有的收益高，不用对比 dp[len-1][0]
    }
}
